/*
 * main.cpp
 *
 *  Created on: Jul 28, 2012
 *      Author: hxu
 *      Questions in Cracking coding interview, Chapter 3
 */

#include<iostream>
#include<string>
#include "stack.h"
#include<sstream>
#define N 10

using namespace std;

void hanoi_tower(stack& st1, stack& st2, stack& st3, int n);

int main(int argc, char * argv[]) {
	cout << " Questions in Chapter 3, Cracking coding interview." << endl;
	stack st1(N), st2(N), st3(N);

	//// read in inputs
	//for(int i=1;i<=argc-1;i++){
	//	//cout << argv[i] << endl;
	//	str_in.append(argv[i]);
	//	str_in.append(" ");
	//}

	try {
		for(int i=N-1;i>=0;i--){
			//
			st1.push(i);
		}
		hanoi_tower(st1, st2, st3, N);
		cout << " St1: " << st1 << endl;
		cout << " St2: " << st2 << endl;
		cout << " St3: " << st3 << endl;
	} catch (string& err) {
		cout << " Error: " << err << endl;
		return 0;
	} catch (exception& e) {
		cout << " Error: " << e.what() << endl;
		return 0;
	}

	cout << " Mission complete!" << endl;

	cin.get();

	return 1;
}

void hanoi_tower(stack& st1, stack& st2, stack& st3, int n){
	// hanoi_tower, move n elements from st1 to st3, by st2	
	int* tmp = NULL;
	bool suc = false;
	stringstream errstream;

	if(n==1){
		tmp = st1.pop();
		if(tmp==NULL){
			errstream << " Element " << n << " is out of size of st1!";
			throw(errstream.str());
		}
		suc = st3.push(*tmp);
		if(suc==false)
			throw(" St3 is full!");
		delete tmp;
		return;
	}

	// move the upper n-1 elements from st1
	hanoi_tower(st1, st2, st3, n-1);

	// move the nth element
	tmp = st1.pop();
	if(tmp==NULL){
		errstream << " Element " << n << " is out of size of st1!";
		throw(errstream.str());
	}
	
	suc = st2.push(*tmp);
	if(suc==false){
		throw(" St2 is full!");
	}

	// move the upper n-1 elements from st3
	hanoi_tower(st3, st2, st1, n-1);

	// push n to st3
	tmp = st2.pop();
	if(tmp==NULL)
		throw(" St2 is empty!");
	suc = st3.push(*tmp);
	if(suc==false){
		throw(" St3 is full!");
	}

	// move the upper n-1 elements back to st3
	hanoi_tower(st1, st2, st3, n-1);


	delete tmp;
}